#include<iostream>
using namespace std;

class Solution {
public:
    int fib(int n) {
        if(n<=1)return n;
        int f0=0;
        int f1=1;
        int s = 0;
        for (int i = 2; i <= n; i++)
        {
            s = (f0+f1)%1000000007;
            f0 = f1;
            f1 =s;
        }
        return s;
    }
};